2390. Разбиения на слагаемые

Перечислите все разбиения целого положительного числа n на целые положительные слагаемые. Разбиения должны обладать следующими свойствами:

· Слагаемые в разбиениях идут в невозрастающем порядке.

· Разбиения перечисляются в лексикографическом порядке.

Вход. Содержит единственное целое число n (1 ≤ n ≤ 40).

Выход. Выведите искомые разбиения по одному в строке.

Пример входа	Пример выхода
4	1 1 1 1 2 1 1 2 2 3 1 4

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть n = x₁ + x₂ + … + x_k – разбиение числа n на натуральные слагаемые. Исходя из условия задачи, слагаемые любого разбиения удовлетворяют неравенству: x₁ ³ x₂ ³ … ³ x_k. x₁ может принимать значения от 1 до n, а каждое x_i (2 £ i £ k) может принимать значение от 1 до x_i-1. То есть следует сгенерировать все возможные последовательности x₁, x₂, …, x_k, удовлетворяющие выше приведенным условиям. Рекурсивность процедуры генерации разбиений состоит в том, что если при разбиении числа n в качестве первого слагаемого выбрано x₁ (x₁ £ n), то далее необходимо генерировать все возможные разбиения числа n – x₁ со слагаемыми, не большими x₁.

Реализация алгоритма

В массиве x будем генерировать разбиения числа n.

int x[50];

Функция f генерирует разбиения числа number и имеет три аргумента:

· pos – текущая позиция в массиве x,

· max – максимально возможное слагаемое, которое может находиться в позиции pos,

· number – число, которое разбивается.

void f(int pos, int max, int number)

{

Если разбиваемое число number равно нулю, то выводим текущее разбиение, построенное в массиве x.

if (number == 0)

{

for (int i = 0; i < pos; i++)

printf("%d ", x[i]);

printf("\n");

return;

}

В позиции pos массива x может находиться любое число от 1 до min(max, number).

for (int i = 1; i <= min(max, number); i++)

{

x[pos] = i;

f(pos + 1, i, number - i);

}

}

Основная часть программы. Читаем входное значение n и запускаем генерацию всех разбиений.

scanf("%d",&n);

f(0,n,n);